package leetcode.offer_two_special.tree;

import leetcode.tree.common.TreeNode;

import java.util.Stack;

/**
 * @author mazouri
 * @create 2021-09-12 18:15
 */
public class _53_inorderSuccessor {
    public TreeNode inorderSuccessor1(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        TreeNode res = null;

        while (cur != null) {
            if (cur.val > p.val) {
                res = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return res;
    }

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        boolean found = false;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();

            if (found) break;
            else if (p == cur) found = true;

            cur = cur.right;
        }
        return cur;
    }
}
